
/*
Description:
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3
*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

/**
* Definition for singly-linked list.
*/
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
	ListNode * deleteDuplicates(ListNode* head) {
		if (!head) return NULL;
		ListNode* p = new ListNode(head->val - 1), *ptr = p, *pre = p;
		while (head) {
			if (pre->val != head->val && (!head->next || head->next->val != head->val)) {
				ptr->next = head;
				ptr = ptr->next;
			}
			pre = head;
			head = head->next;
		}
		ptr->next = NULL;
		return p->next;
	}

	ListNode * deleteDuplicates3(ListNode* head) {
		ListNode* dummy = new ListNode(0);
		dummy->next = head;
		ListNode* cur = dummy;
		int duplicate;
		while (cur->next && cur->next->next) {
			if (cur->next->val == cur->next->next->val) {
				duplicate = cur->next->val;
				while (cur->next && cur->next->val == duplicate) {
					cur->next = cur->next->next;
				}
			}
			else {
				cur = cur->next;
			}
		}
		return dummy->next;
	}

	ListNode * deleteDuplicates2(ListNode *head) {
		ListNode **runner = &head;

		if (!head || !head->next)return head;

		while (*runner)
		{
			if ((*runner)->next && (*runner)->next->val == (*runner)->val)
			{
				ListNode *temp = *runner;
				while (temp && (*runner)->val == temp->val)
					temp = temp->next;

				*runner = temp;
			}
			else
				runner = &((*runner)->next);
		}

		return head;
	}

	ListNode * deleteDuplicates1(ListNode* head) {
		if (!head) return 0;
		if (!head->next) return head;

		int val = head->val;
		ListNode* p = head->next;

		if (p->val != val) {
			head->next = deleteDuplicates(p);
			return head;
		}
		else {
			while (p && p->val == val) p = p->next;
			return deleteDuplicates(p);
		}
	}

	ListNode * deleteDuplicates0(ListNode* head) {
		int n;				
		ListNode *phead = new ListNode(0);
		phead->next = head;
		ListNode *p = phead;


		if (head == nullptr)
		{
			return head;			
		}			
		else
		{
			n = head->val;
			//p = p->next;
		}			

		while (p->next->next)
		{
			if (p->next->next->val == n)
			{
				while (p->next->next)
				{
					if (p->next->next->val == n)
					{
						p->next->next = p->next->next->next;
					}
					else
					{
						n = p->next->next->val;

						if (phead->next == p->next)
						{
							phead->next = p->next->next;
						}
						p->next = p->next->next;
						//p = p->next;
						break;
					}
				}								
			}
			else
			{
				n = p->next->next->val;
				p = p->next;
			}
		}

		return phead->next;
	}
};

int _deleteDuplicates2()
{
	vector<int> nums{1,1,1,2,3};// { 1, 2, 3, 3, 4, 4, 5 };
	ListNode *phead = new ListNode(0);
	
	Solution solu;
	ListNode *dl;
	ListNode *p;
	
	p = phead;
	for (auto n : nums)
	{
		p->next = new ListNode(n);
		p = p->next;
	}

	cout << "orginal list: " << endl;
	p = phead->next;
	while (p)
	{
		cout << p->val << " ";
		p = p->next;
	}
	cout << endl;

	dl = solu.deleteDuplicates(phead->next);	
	
	cout << "distinct list: " << endl;
	p = dl;
	while (p)
	{
		cout << p->val << " ";
		p = p->next;
	}
	cout << endl;
	return 0;
}